﻿
namespace Leetcode.N0164;
public class Solution
{
    public int MaximumGap(int[] nums)
    {
        if (nums.Length < 2)
        {
            return 0;
        }
        var max = 0;
        this.Sort(ref nums);

        for (int i = 1; i < nums.Length; i++)
        {
            max = Math.Max(max, nums[i] - nums[i - 1]);
        }

        return max;
    }

    // 基数排序
    protected internal void Sort(ref int[] nums)
    {
        int position = 1;
        bool isContinue = true;
        while (isContinue)
        {
            var dights = new int[10];
            for (int i = 0; i < nums.Length; i++)
            {
                int n = (int)(nums[i] % Math.Pow(10, position) / Math.Pow(10, position - 1));
                dights[n] += 1;
            }

            var sum = 0;
            for (int i = 0; i < dights.Length; i++)
            {
                var t = dights[i];
                dights[i] = sum;
                sum += t;
            }


            var tmp = new int[nums.Length];
            var baseValue = Math.Pow(10, position);
            isContinue = false;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] >= baseValue)
                {
                    isContinue = true;
                }

                int n = (int)(nums[i] % Math.Pow(10, position) / Math.Pow(10, position - 1));
                tmp[dights[n]] = nums[i];
                dights[n]++;
            }
            nums = tmp;
            position++;
        }

    }
}
